|
Correlation in Games
Adam Brandenburger, University of New York, USA
Correlation is a basic concept in game theory (GT), going back to von Neumann-Morgenstern (1944).
Yet the non-cooperative branch in GT assumes that players do not coordinate their strategies so,
where do correlations come from in this case? There are two routes to answering
this question, each corresponding to a different view of a game.
The first view is that the game as given is a complete description. (See "Intrinsic Correlation
in Games", with Amanda Friedenberg, 2004, www.stern.nyu.edu/~abranden.)
Under this approach, the variables used to generate correlations are the
players' beliefs about how the game will be played (including their beliefs
about other players' beliefs, etc.). This route leads to an impossibility result:
There are correlations that cannot arise via this method.
The second view is that the game as given is an incomplete description.
(See "Subjectivity and Randomization in Correlated Strategies", by Robert
Aumann, /Journal of Mathematical Economics/, 1974.) Hidden variables outside
the given game are then used to generate correlations.
These two routes in GT parallel the two routes to explaining correlations in quantum mechanics
(QM): The Einstein-Podolsky-Rosen Paradox (1935) supposes QM is complete, while
Bell's Theorem (1964) allows that QM is incomplete. We use this parallel
to produce a game based on a variant of Bell's Theorem ("Nonlocality for
Two Particles without Inequalities for Almost All Entangled States", by
Lucien Hardy, /Foundations of Physics/, 1993). In this game, there are
correlations that cannot be explained even via hidden variables. (See "A
Connection Between Correlation in Game Theory and Quantum Mechanics",
with Amanda Friedenberg, 2006, www.stern.nyu.edu/~abranden.) We discuss
implications for GT.
Social Choice Over Combinatorial Domains
Jerome Lang, Universite Paul Sabatier, France
In many real-world social choice problems, the set of alternatives is
defined as the Cartesian product of (finite) domain values for each of a
given set of variables. Examples of such problems are multi-issue
referenda, fair allocation of indivisible goods etc. Such combinatorial
domains are much too large to allow for representing preference relations
or utility functions explicitly, which has lead AI researchers to develop
languages for compact preference representation, which exploit structural
properties such as conditional preferential independencies between some of
the variables. Moreover, due again to the size of the domains, usual
social choice procedures cannot be applied in a straightforward way, which
calls for but instead should be decomposed into smaller subproblems and/or
approximated.
The talk will be structured in three parts : (a) brief background on
compact preference representation for combinatorial domains; (b) voting
and aggregation on combinatorial domains; (c) fair division of indivisible
items. It is half way between a survey talk and an exposition of some
works I've been involved in.
Pre-Bayesian Games
Moshe Tennenholtz, Technion, Israel
Work on modelling uncertainty in game theory and economics almost
always uses Bayesian assumptions. On the other hand, work in computer
science frequently uses non-Bayesian assumptions and appeal to forms
of worst case analysis.
In this talk we deal with Pre-Bayesian games, games
with incomplete information but with no probabilistic assumptions about
the environment. We first discuss safety-level, minmax regret, and
competitive ratio equilibria, and their existence in a general setting. Our
study then concentrates on safety-level equilibrium and its use when
incorporating uncertainty into congestion settings. In particular, we show
that the lack of knowledge on the number of participants is beneficial to
the society in any linear resource selection game. Next we introduce
efficient learning equilibrium [ELE], a form of ex-post equilibrium for
Pre-Bayesian repeated (and more generally, stochastic) games. ELE is a
solution concept for learning in games, where the learning algorithms
themselves are required to be in equilibrium for a whole class of
games. We prove the (constructive) existence of ELE for some rich
settings.
The talk will be a brief and somewhat informal introduction to
our work on Pre-Bayesian games. The particular results which will be
presented are based on joint work with Itai Ashlagi, Ronen Brafman, and Dov
Monderer. If time permits we will add few words on some of the other
lines of research (all dealing with the interplay between game theory and
computer science) we are currently involved with.
|
